package LeetCode.TwoPointers;

import java.util.Stack;

/**
 * @author : LdLtd
 * @Date : 2023/7/23
 * @Description:42. 接雨水
 */
public class trapping_rain_water {
    public static void main(String[] args) {
         Solution solution = new Solution();
        int[] ints = {4,2,0,3,2,5};
        System.out.println(solution.trap1(ints));
    }
    static class Solution {
        /*一行一行的求 从左边开始，当t小于i时候+1,当t大于等于i时结算
        * 时间复杂度：如果最大的数是 mm，个数是 nn，那么就是 O(m*n)。
        空间复杂度：O(1)O。*/
        public int trap1(int[] height) {
            int res=0,t=0;
            boolean flag=false;
            //求最高层，方便确定遍历的次数
            int maxh=getMax(height);
            for (int i = 0; i <=maxh; i++) {
                //标记是否更新
                flag=false;
                t=0;
                for (int j = 0; j < height.length; j++) {
                    if(flag&&height[j]<i){
                        t++;
                    }
                    if(height[j]>=i){
                        res+=t;
                        t=0;
                        flag=true;
                    }
                }

            }
            return res;
        }
        private int getMax(int[] height){
            int res=0;
            for (int i = 0; i < height.length; i++) {
                if(height[i]>res) res=height[i];
            }
            return res;
        }
        /*一列一列的求，每次只考虑左右两边最高的墙，当前列的水就是其中最小的那一个剪当前列
        * 时间复杂度：O(n²），遍历每一列需要 nn，找出左边最高和右边最高的墙加起来刚好又是一个 nn，所以是 n²。
        空间复杂度：O(1）*/
        public int trap2(int[] height) {
            int res=0,l=0,r=0;
            //最左边的不考虑，一定没有，所以下标从1到length-2;
            for (int i = 1; i < height.length-1; i++) {
                l=0;
                for (int j = i-1; j >=0 ; j--) {
                    if(height[j]>l) l=height[j];
                }
                r=0;
                for (int j = i+1;j< height.length-1 ; j++) {
                    if(height[j]>r) r=height[j];
                }
                int min=Math.min(l,r);
                if(min>height[i]) res+=min-height[i];
            }
            return res;
        }
        /*
        * 动态规划，每次求最高最低的时候，
        * 对于 max_left我们其实可以这样求。

        l[i] = Max(l [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。

        对于 r我们可以这样求。

        r[i] = Max(r[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
        * 时间复杂度：O(n)
        空间复杂度：O(n)，用来保存每一列左边最高的墙和右边最高的墙
*/
        public int trap3(int[] height) {
            int res=0;
            int h=height.length;
            int [] l=new int[h];
            int [] r=new int[h];
            //求每个点左边的最大
            for (int i = 0; i < h-1; i++) {
                l[i]=Math.max(l[i-1],height[i-1]);
            }
            //求每个点右边的最大
            for (int i = h-2; i >=0; i--) {
                r[i]=Math.max(r[i+1],height[i+1]);
            }
//            求值
            for (int i = 0; i < h-1; i++) {
                int min=Math.min(l[i],r[i]);
                if(min>height[i]) res+=min-height[i];
            }
            return  res;
        }

        /*双指针
        * 对空间复杂度进行进一步的优化。

        例如这道题中，可以看到，l [ i ] 和 r [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。
        所以我们可以不用数组，只用一个元素就行了。我们先改造下 l。
        * maxl = Math.max(maxl, height[i - 1]);
        * 而maxr是从右往左的，求值是从左往右，还不能去掉
        * 所以采用两个指针，依次更新左右两格的接水
        */
        public int trap4(int[] height) {
            int res=0,l=1,r=height.length-2,maxl=0,maxr=0;
            for (int i = 1; i < height.length-1; i++) {
                //从左往右
                if(height[l-1]<height[r+1]){
                    maxl=Math.max(maxl,height[l-1]);
                    int min=maxl;
                    if(min>height[l]){
                        res+=min-height[l];
                    }
                    l++;
                    //从右往左
                }else{
                    maxr=Math.max(maxr,height[r+1]);
                    int min=maxr;
                    if(min>height[r]){
                        res+=min-height[r];
                    }
                    r--;
                }
            }
            /*第二种写法*/
       /*     while(l<r){
                maxl=Math.max(maxl,height[l]);
                maxr=Math.max(maxr,height[r]);
                if(height[l]<height[r]){
                    res+=maxl-height[l];
                    l++;
                }else {
                    res+=maxr-height[r];
                    r++;
                }
            }*/
            return res;
        }
        /*单调栈
        * 总体的原则就是，

1当前高度小于等于栈顶高度，入栈，指针后移。
2当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，
* 重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
*
*
* 时间复杂度：虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 O(n)。

空间复杂度：O(n)。栈的空间。


*/
        public int trap5(int[] height) {
            int res=0;
            Stack<Integer> stack = new Stack<>();
            int current=0;
            while (current<height.length){
                //如果栈不为空且当前的高度大于栈顶高度就一直拿出
                while(!stack.empty()&&height[current]>height[stack.peek()]){
                    //出栈
                    int pop = stack.pop();
                    //栈空结束
                    if(stack.isEmpty()) break;
                    int l = stack.peek();
                    //两墙距离
                    int currWidth=current-l-1;
                    //高度
                    int currHeight = Math.min(height[stack.peek()], height[current])-height[pop];
                    res+=currWidth*currHeight;
                }
                //否则把当前指向的墙入栈，且指针后移
                stack.push(current++);
            }
            return res;
        }
    }
}
